package com.framework.admin.util;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeUtil {
    /**
     * @param treeListIn   传入树
     * @param treeOutClass 输出泛型 .class
     * @param function     回调函数 结果 treeOut
     * @param <TreeIn>     传入树泛型
     * @param <TreeOut>    输出树泛型
     * @return
     */
    public static <TreeIn extends ITree<TreeIn>, TreeOut extends ITree<TreeOut>> List<TreeOut> treeEach(List<TreeIn> treeListIn, Class<TreeOut> treeOutClass, ITreeFunction<TreeIn, TreeOut> function) {
        //  原树形 栈
        Stack<TreeIn> oprStack = new Stack<>();

        //  存放转换后的视图的栈
        Stack<TreeOut> voStack = new Stack<>();
        //  深度优先遍历
        //  一级节点入栈
        treeListIn.forEach(node -> {
            oprStack.push(node);
        });
        while (!oprStack.empty()) {
            TreeIn inNode = oprStack.pop();
            //  栈顶节点存在子节点时展开，并将子节点全部入栈
            if (inNode.getChildren() != null && inNode.getChildren().size() > 0) {
                oprStack.push(inNode);
                for (TreeIn chd : inNode.getChildren()) {
                    oprStack.push(chd);
                }
                inNode.setChildren(null);
            } else {
                //  执行节点处理任务
                TreeOut outNode = function.exec(inNode);
                //  比较原节点栈和视图栈顶元素大小。
                //  如果栈为空就将原节点加入视图栈
                if (voStack.empty()) {
                    voStack.push(outNode);
                    continue;
                }
                //  如果两个节点 树深度相同，或者原节点树深度更低，就将原节点加入视图栈
                if (outNode.getTreeLevel() >= voStack.peek().getTreeLevel()) {
                    voStack.push(outNode);
                    continue;
                }
                //  如果原节点级别更高，就将视图栈的节点出栈，直到和原节点级别一样为止，作为其子节点
                //  然后将原节点入栈
                if (outNode.getTreeLevel() < voStack.peek().getTreeLevel()) {
                    outNode.setChildren(new ArrayList<>());
                    while (!voStack.empty() && voStack.peek().getTreeLevel() > outNode.getTreeLevel()) {
                        outNode.getChildren().add(voStack.pop());
                    }
                    voStack.push(outNode);
                    continue;
                }
            }
        }
        //  原栈空后将全部节点取出，作为list返回
        List<TreeOut> treeOutList = new ArrayList<>();
        while (!voStack.empty()) {
            treeOutList.add(voStack.pop());
        }
        return treeOutList;
    }
}
